//
//  IntegerBreak.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/30.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  343. 整数拆分

import UIKit

/*
 343. 整数拆分
 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

 示例 1:

 输入: 2
 输出: 1
 解释: 2 = 1 + 1, 1 × 1 = 1。
 示例 2:

 输入: 10
 输出: 36
 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 说明: 你可以假设 n 不小于 2 且不大于 58。
 */

class IntegerBreak: NSObject {
    /*
     动态规划解法
     
     对于正整数n，当 n >= 2 时，可以拆分成至少两个正整数。
     设 k 是拆出来的第一个正整数，那么剩下的部分就是 n-k ，n-k可以继续拆成至少两个正整数，或者不拆分。
     由于每个正整数的最大乘积取决于比它小的正整数对应的最大乘积，因此可以用动态规划法求解。
     
     创建数组dp，其中第dp[i]表示整数i可以拆分成至少两个正整数之后，这些整数的最大乘积。
     边界情况有0，1不可拆分。因此 dp[0] = dp[1] = 0
     
     当 i >= 2 时，假设第一个拆出来的正整数是 j(1<=j<i)，则有以下两种方案
     - 将i分成 j 和 i-j，且 i-j 不再继续分割。此时乘积是 j*(i-j)
     - 将i分成 j 和 i-j，且 i-j 继续拆分。此时乘积是 j*dp[i-j]
     
     因此，当 j 固定时，有dp[i] = max(j*(i-j),j*dp[i-j])。
     由于j的取值范围是1 ~ i-1，需要遍历所有的 j 得到dp[i]的最大值，因此可以得到状态转移方程
     
     dp[i] =  max{max(j*(i-j),j*dp[i-j])}
             1<=j<i
 
     最终得到dp[n]的值即为该题结果
     */
    
    func integerBreak(_ n: Int) -> Int {
        
        var dp = [Int](repeating: 0, count: n+1)
        
        //dp[0] = 0
        //dp[1] = 0
        
        for i in 2 ... n {
            var maxValue = 0
            for j in 1 ..< i {
                maxValue = max(maxValue, max(j*(i-j), j*dp[i-j]))
            }
            dp[i] = maxValue
        }
        
        return dp[n]
    }
    
    
    /*
     动态规划优化
     当 i >= 3 时，状态转移方程：
     dp[i] = max(2*(i-2), 2*dp[i-2], 3*(i-3), 3*dp[i-3])
     
     */
    func integerBreak2(_ n: Int) -> Int {
        if n < 4{
            return n-1
        }
        var dp = [Int](repeating: 0, count: n+1)
        dp[2] = 1
        
        for i in 3 ... n{
            dp[i] = max(max(2*(i-2), 2*dp[i-2]), max(3*(i-3), 3*dp[i-3]))
        }
        return dp[n]
    }
    
    
    //其他解法
    //分析一下就有从n=7开始，dp[n] = 3*dp[n-3]
    
    /*
    //根据数学发可知 本题分割成3是最优解
    func integerBreak3(_ n: Int) -> Int {
        if n <= 3{
            return n - 1
        }
        var quotinet = n/3
        var remainder = n%3
        if remainder == 0 {
            return Int(pow(3, quotinet))
        }else if remainder == 1{
            return Int(pow(3, quotinet-1))*4
        }else{
            return Int(pow(3, quotinet))*2
        }
    }
    */
}
